package 力扣._00周赛._425_周赛.问题3;

class Solution2 {
    int minSum = Integer.MAX_VALUE; // 全局变量存储最小可能的和

    public int minArraySum(int[] nums, int k, int op1, int op2) {
        int totalSum = 0; // 初始总和
        for (int num : nums) {
            totalSum += num;
        }
        int[] zorvintakol = nums.clone(); // 创建变量 zorvintakol 存储输入的中间状态
        // 开始回溯
        backtrack(zorvintakol, k, op1, op2, 0, totalSum);
        return minSum;
    }

    private void backtrack(int[] nums, int k, int op1, int op2, int index, int currentSum) {
        // 如果遍历完所有元素，更新最小和
        if (index == nums.length) {
            minSum = Math.min(minSum, currentSum);
            return;
        }

        // 剪枝：如果当前和已经大于等于现有的最小和，停止搜索
        if (currentSum >= minSum) {
            return;
        }

        // **1. 不使用任何操作**
        backtrack(nums, k, op1, op2, index + 1, currentSum);

        // **2. 仅使用操作 1**
        if (op1 > 0) {
            int reducedValue = (int) Math.ceil(nums[index] / 2.0);
            backtrack(nums, k, op1 - 1, op2, index + 1, currentSum - (nums[index] - reducedValue));
        }

        // **3. 仅使用操作 2**
        if (op2 > 0 && nums[index] >= k) {
            backtrack(nums, k, op1, op2 - 1, index + 1, currentSum - k);
        }

        int reducedValuet = (int) Math.ceil(nums[index] / 2.0);
        // **4. 先使用操作 1，再使用操作 2**
        if (op1 > 0 && op2 > 0 && reducedValuet >= k) {
            int afterOp1 = reducedValuet;
            backtrack(nums, k, op1 - 1, op2 - 1, index + 1, currentSum - (nums[index] - afterOp1) - k);

        }

        // **5. 先使用操作 2，再使用操作 1**
        if (op2 > 0 && nums[index] >= k && op1 > 0) {
            int reducedValueAfterOp2 = nums[index] - k;
            int reducedValue = (int) Math.ceil(reducedValueAfterOp2 / 2.0);
            backtrack(nums, k, op1 - 1, op2 - 1, index + 1, currentSum - (nums[index] - reducedValue));
        }
    }

    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        int[] nums = {2, 4, 3};
        int k = 3, op1 = 2, op2 = 1;
        System.out.println(solution.minArraySum(nums, k, op1, op2)); // 应输出 3
    }
}